package mao.leetcode.others.leetcode117;



import java.util.LinkedList;
import java.util.Queue;


public class Solution {
    //二叉树分层遍历，太耗费时间。
    public Node connect(Node root) {
        if (root == null) return root;
        Queue<Node> q = new LinkedList<Node>() ;
        q.offer(root);
        Node node_1;
        Node node_2;
        while ( !q.isEmpty() ){
            int size = q.size();
            node_1 = q.poll();
            if (node_1.left != null)   q.offer(node_1.left);
            if( node_1.right != null) q.offer(node_1.right);
            for (int i = 0; i < size-1; i++) {
                  node_2 = q.poll();
                  node_1.next=node_2;
                  node_1=node_2;
                 if (node_1.left != null)   q.offer(node_1.left);
                 if( node_1.right != null)  q.offer(node_1.right);
            }
        }
        return root;
    }

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;
        public Node() {}
        public Node(int _val,Node _left,Node _right,Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };
}
